package com.it.data_sort;

/**
 * @Author: CaoYouGen
 * @DateTime: 2023/05/18/13:11
 * @注释: 快速排序
 **/
public class QuickSort {

    /**
     * @Author: CaoYouGen
     * @注释: 快速排序
     * @DateTime: 2023/5/18 15:04
     *
     * @param arr:  arr 待排序的数组
     * @return void
     */
    public static void quickSort(int[] arr){
        // 判断传入的数组是否为空 或者 长度是否为0
        if (arr == null || arr.length == 0){
            return;
        }
        // 执行排序逻辑
        sort(arr,0, arr.length - 1);
    }


    /**
     * @Author: CaoYouGen
     * @注释: 快速排序（执行排序逻辑）
     * @DateTime: 2023/5/18 15:06
     *
     * @param arr: arr 待排序的数组
     * @param left: 左边界
     * @param right:  右边界
     * @return void
     */
    private static void sort(int[] arr, int left, int right){
        // 判断左指针是否大于等于右指针 是 代表已经判断完
        if (left >= right){
            return;
        }
        // 设置左右指针 和 基准值
        int l = left, r = right, pivot = arr[(left + right) >>> 1];

        // 开始分区
        while (l <= r){
            // 左边指针一直向右移动 直到找到一个大于等于基准值的
            while (arr[l] < pivot){
                l++;
            }
            // 右指针一直向左移动 直到找到一个小于等于基准值的
            while (arr[r] > pivot){
                r--;
            }
            // 如果左指针 小于 右指针 说明左指针所指的数应该在右边 右指针所指的数应该在左边（交换位置）
            if (l <= r){
                int item = arr[r];
                arr[r] = arr[l];
                arr[l] = item;
                l++;
                r--;
            }
            // 分别对左右两个区域进行递归调用
            sort(arr,left,r);
            sort(arr,l,right);
        }

    }





}
